The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Internet protocol relates to a network layer protocol in the TCP/IP stack offering a connectionless inter-network service. Various routing protocols have been used to implement such networks. In particular, Link State Protocols have proved popular in which data is transmitted using Link State Packets. An example of such a protocol is the Intermediate System-to-Intermediate System (IS-IS) protocol.
A network comprises a plurality of nodes connected together. Some nodes represent end systems (such as printers, fax machines, telephones, PC's etc) whereas other nodes represent network devices (e.g. switches, routers etc). Data packets are sent around the network from a source to a destination in accordance with routing information shared among the nodes of the network. As the network comprises a plurality of interconnected nodes, the network is fairly robust. Should a node fail for any reason, the network dynamically configures to re-route data so as to avoid the failed node.
Discovery messages, such as Hello messages, provide a mechanism by which nodes on a network may continually indicate their presence. The “Hello” packets are used to establish routing adjacencies between directly connected routers and for the purpose of exchanging routing information packets.
A link can be thought of as an interface on a router. The state of the link is a description of that interface and of its relationship to its neighboring routers. A description of the interface would include, for example, the IP address of the interface, the mask, the type of network it is connected to, the router connected to that network and so on. The collection of all these link-states form a link-state database. Link state protocols use a link state algorithm to build and calculate the shortest path to all known destinations. The algorithms themselves are quite complicated but the following provides a high level simplified way of looking at the various steps of a link state algorithm. Upon initialization or due to any changing routing information, a router will generate a link state advertisement. This advertisement represents the collection of all link states on that router. All routers exchange link states by means of flooding. Each router that receives a link state update, stores a copy in its link state database and then propagates the update to other routers. After the database of each router is completed, the router will calculate the shortest path tree to all designations and use this information to form an IP routing table.
In IS-IS, when a link or a node fails and is subsequently repaired, the routers involved with the repaired part of the network then have to re-establish an IS-IS adjacency over that link. This is achieved by the router(s) transmitting Hello packets and receiving in response Hello packets from their neighboring nodes. The router then generates an adjacency table with information received from the neighboring nodes and updates its Link-State Protocol data unit (LSP) and floods it throughout the network area. Link-state routing protocols mean that each router in the area, after having received a LSP, will compute a Shortest Path First and update its IP routing table.
The LSP as sent by the router advertises adjacency information regardless of whether the routers are effectively able to forward traffic. When a router or a link has been down, there are additional delays whilst the routers obtain full knowledge of the forwarding cache and until the Border Gateway Protocol (BGP) has also converged (if needed). Until these occur, the router is not in a state to forward data sent to it for onward routing.
The IS-IS protocol already includes some mechanisms to prevent the router being used as a transit node in another router's table until its convergence is finished. Typically the overload bit LSPDBOL is set whilst the system is converging. At the same time the adjacency of the LSP is advertised. However, this allows a receiving router to compute routes towards a re-starting node before such a node is ready for data.
When a router restarts, it originates its LSP with a sequence number of 1. As there will be old versions of the old LSP for the restarting router already existing in the network, its neighbors will flood back the old copy of the restarting router LSP (if any) with the last sequence number used before the restart. LSPs are kept in link state databases for a significant amount of time. Therefore the LSP of a restarting router will survive in the database of other routers in the network. On receipt of the old copy of the restarting router LSP, the restarting router can determine the next sequence number it has to use and regenerates its LSP with a sequence number higher than the one received on the old copy of its LSP. Such LSP exchange takes time and until it is finished all routers in the area may compute their SPF using an old copy of the restarting router LSP. Therefore routers in the network may route data to the restarting router before it is fully converged.
Based on the foregoing, there is a clear need for a method of preventing routers in the network from routing data to a restarting router before the router has fully converged.